package sort;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 3, 1, 6, 8, 3, 7};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void heapSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, i, n);
        }
        for (int i = n - 1; i >= 0; i--) {
            swap(nums, 0, i);
            heapify(nums, 0, --n);
        }
    }

    public static void heapify(int[] nums, int i, int n) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int index = i;
        if (left < n && nums[left] > nums[index]) {
            index = left;
        }
        if (right < n && nums[right] > nums[index]) {
            index = right;
        }
        if (index != i) {
            swap(nums, i, index);
            heapify(nums, index, n);
        }
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }


}
